#include <vector>
#include <exception>
#include <iostream>

using namespace std;


typedef exception BadIterator;  //This is a simplification of the exception class.  In a real implementation care would be taken to return the right error message.

template <class Object>
class LList;     // Incomplete declaration.

template <class Object>
class LListItr;  // Incomplete declaration.

// LListNode class
template <class Object>
class LListNode
{
	LListNode( const Object & theElement = Object( ),
			LListNode * n = NULL )
		: element( theElement ), next( n ) { }

	Object     element;
	LListNode *next;

	friend class LList<Object>;
	friend class LListItr<Object>;
};

// LList class
template <class Object>
class LList
{
	public:
		LList( );
		~LList( );

		bool isEmpty( ) const;
		void makeEmpty( );

		LListItr<Object> first( ) const;
		LListItr<Object> zeroth( ) const;

		void remove( const Object & x);
		LListItr<Object> findPrevious( const Object & x ) const;
		void insert( const Object & x, const LListItr<Object> & p );

		void push_front(const Object& obj);
		void pop_front();
		size_t size() const;
		void reverse();
		void unique();

	private:
		LListNode<Object> *header;
		size_t items;
};


// LListItr class
template <class Object>
class LListItr
{
	public:
		LListItr( ) : current( NULL ) { }

		void operator++( );
		Object & operator*( ) const;
		bool operator==(LListItr<Object> rhs) const;
		bool operator!=(LListItr<Object> rhs) const;

		bool isPastEnd( ) const
		{ return current == NULL; }

	private:
		LListNode<Object> *current;    // Current position

		LListItr( LListNode<Object> *theNode )
			: current( theNode ) { }

		friend class LList<Object>; // Grant access to constructor
};



//************************** #2 LListItr Parts **************************************

// increment
template <class Object>
void LListItr<Object>::operator++(){
	current = current->next;
}

//deref
template <class Object>
Object& LListItr<Object>::operator*()const{
	return current->element;
}

//equality
template <class Object>
bool LListItr<Object>::operator==(LListItr<Object> rhs) const {
	return current == rhs.current;
}

template <class Object>
bool LListItr<Object>::operator!=(LListItr<Object> rhs) const {
	return current != rhs.current;
}

//***********************************************************************************

// Construct the list.
	template <class Object>
LList<Object>::LList( )
{
	items = 0;
	header = new LListNode<Object>;
}

// Destructor.
	template <class Object>
LList<Object>::~LList( )
{
	makeEmpty( );
	delete header;
}

// Test if the list is logically empty.
// Return true if empty, false, otherwise.
template <class Object>
bool LList<Object>::isEmpty( ) const
{
	return header->next == NULL;
}

// Make the list logically empty.
	template <class Object>
void LList<Object>::makeEmpty( )
{
	while( !isEmpty( ) )
		remove( *first( ) );
	items = 0;
}

// Return an iterator representing the header node.
template <class Object>
LListItr<Object> LList<Object>::zeroth( ) const
{
	return LListItr<Object>( header );
}

// Return an iterator representing the first node in the list.
// This operation is valid for empty lists.
template <class Object>
LListItr<Object> LList<Object>::first( ) const
{
	return LListItr<Object>( header->next );
}

// Insert item x after p.
	template <class Object>
void LList<Object>::insert( const Object & x, const LListItr<Object> & p )
{
	if( p.current != NULL )
	{
		p.current->next = new LListNode<Object>( x, p.current->next );
	}
	items++;
}

// Remove the first occurrence of an item x.
	template <class Object>
void LList<Object>::remove( const Object & x )
{
	LListNode<Object> *p = findPrevious( x ).current;

	if( p->next != NULL )
	{
		LListNode<Object> *oldNode = p->next;
		p->next = p->next->next;  // Bypass deleted node
		delete oldNode;
	}
	items--;
}

// Return iterator prior to the first node containing an item x.
template <class Object>
LListItr<Object> LList<Object>::findPrevious( const Object & x ) const
{
	LListNode<Object> *p = header;

	while( p->next != NULL && p->next->element != x )
		p = p->next;

	return LListItr<Object>( p );
}


//*********************** #2 LList methods ******************************************
template <class Object>
size_t LList<Object>::size()const{
	return items;
}

template <class Object>
void LList<Object>::push_front(const Object& x){
	insert(x, zeroth());
}

template <class Object>
void LList<Object>::pop_front(){
	remove(*first());	//looks dubious but because I am always looking for the very first element remove will always be it's best-case which is O(1)
}

template <class Object>
void LList<Object>::reverse(){
	vector<Object> v;
	LListItr<Object> itr = first();
	while(!(itr.isPastEnd())){	//save the data
		v.push_back(*itr);
		++itr;
	}
	makeEmpty();			//delete the old stuff
	for(const Object& o : v){
		push_front(o);
	}

}

template <class Object>
void LList<Object>::unique(){
	LListItr<Object> itr = first();
	++itr;	//first element is ignored
	LListItr<Object> trail_itr = first();
	Object lastUni = *first();
	while(!(itr.isPastEnd())){
		if(*itr == lastUni){
			LListNode<Object> *p = trail_itr.current;
			++itr;

			if( p->next != NULL )
			{
				LListNode<Object> *oldNode = p->next;
				p->next = p->next->next;  // Bypass deleted node
				delete oldNode;
			}
			items--;
		}
		else{
			lastUni = *itr;
			++itr;
			++trail_itr;
		}
	}
}

//*********************** #1 advance function ***************************************
/* Preconditions:
   it is pointing to some valid node.
   There are at least n-more elements in the list.
 */

template <class ForwardIterator>
void advance (ForwardIterator& it, int n){
	for(int i = 0; i < n; ++i){
		it++;	//I assume Im allowed to use the operator I wrote.
	}
}

/* Postconditions:
   it is now pointing to the elemen n places after it's original position
 */

//***********************************************************************************

int main(){
	LList<int> ll;
	ll.push_front(1);
	ll.push_front(1);
	ll.push_front(1);
	ll.push_front(4);
	ll.push_front(5);
	ll.insert(6, ll.zeroth());
	ll.insert(7, ll.zeroth());
	ll.insert(8, ll.zeroth());
	ll.insert(8, ll.zeroth());
	ll.insert(8, ll.zeroth());
	cout << ll.size() << endl;
	LListItr<int> itr = ll.first();
	while(!(itr.isPastEnd())){
		cout << *itr << endl;
		++itr;
	}
	ll.pop_front();
	ll.pop_front();
	ll.pop_front();
	ll.pop_front();

	cout << endl << ll.size() << endl;
	itr = ll.first();
	while(!(itr.isPastEnd())){
		cout << *itr << endl;
		++itr;
	}
	
	ll.reverse();

	cout << endl << ll.size() << endl;
	itr = ll.first();
	while(!(itr.isPastEnd())){
		cout << *itr << endl;
		++itr;
	}
	
	ll.unique();

	cout << endl << ll.size() << endl;
	itr = ll.first();
	while(!(itr.isPastEnd())){
		cout << *itr << endl;
		++itr;
	}

}



